package com.tys.algorithm.advanced.test.class02;

//arr中，只有一种数出现奇数次，其他是偶数次
//arr中，有两种数出现奇数次，其他出现偶数次
//统计数N中二进制1的个数
public class Code02_EvenTimesOddTimes {

    public static void printOddTimesNum1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        int eor = 0;
        for (int i = 0; i < arr.length; i++) {
            eor ^= arr[i];
        }
        System.out.println(eor);
    }

    public static void printOddTimesNum2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        int eor = 0;
        for (int i = 0; i < arr.length; i++) {
            eor ^= arr[i];
        }
        int rightOne = eor & ((~eor) + 1);
        int onlyOne = 0;
        for (int i = 0; i < arr.length; i++) {
            if ((arr[i] & rightOne) != 0) {
                onlyOne ^= arr[i];
            }
        }
        System.out.println(onlyOne + " " + (eor ^ onlyOne));
    }

    public static int bit1counts(int num) {
        int count = 0;
        while (num != 0) {
            count++;
            int rightOne = num & ((~num) + 1);
            num ^= rightOne;
        }
        return count;
    }


    public static void main(String[] args) {
        int a = 5;
        int b = 7;

        a = a ^ b;
        b = a ^ b;
        a = a ^ b;

        System.out.println(a + " " + b);
        System.out.println("======使用异或交换期望：7 5========");
        //期望2
        int[] arr1 = {3, 3, 2, 3, 1, 1, 1, 3, 1, 1, 1};
        printOddTimesNum1(arr1);
        System.out.println("=======printOddTimesNum1期望：2=======");

        int[] arr2 = {4, 3, 4, 2, 2, 2, 4, 1, 1, 1, 3, 3, 1, 1, 1, 4, 2, 2};
        printOddTimesNum2(arr2);
        System.out.println("=======printOddTimesNum2期望：3 2=======");

        int n = 4;
        int count = bit1counts(n);
        System.out.println(count);
        System.out.println("======bit1counts期望：1========");


    }

}
